12.4 KB · ⇊ 4 parts · ⤓ Micron 12.4 KB · ⤓ HTML 76.2 KB

top

Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griechisch μικρότατος ‚das kleinste‘). Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind. Eine wichtige echte Teilmenge der μ-rekursiven Funktionen sind die primitiv-rekursiven Funktionen.

Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der Turing-berechenbaren Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem Lambda-Kalkül, Registermaschinen und WHILE-Programmen.

Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn. Die μ-rekursiven Funktionen sind demgegenüber partielle Funktionen, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die Ackermannfunktion.

• Definition des μ-Operators

• Definition der μ-rekursiven Funktionen

• Äquivalenz der μ-rekursiven Funktionen mit der Turingmaschine

• Bemerkung

• Beispiele

• Literatur

Für eine partielle Funktion f : : N k + 1 → → N {\displaystyle f\colon \mathbb {N} ^{k+1}\to \mathbb {N} } und natürliche Zahlen x 1 ; … … ; x k ∈ ∈ N {\displaystyle x_{1};\dots ;x_{k}\in \mathbb {N} } sei die Menge

M ( f , x 1 , … … , x k ) = { n ∈ ∈ N ∣ ∣ f ( x 1 , … … , x k , n ) = 0 ∧ ∧ ∀ ∀ 0 ≤ ≤ m ≤ ≤ n : : f ( x 1 , … … , x k , m ) ↓ ↓ } {\displaystyle M(f,x_{1},\dots ,x_{k})=\{n\in \mathbb {N} \mid f(x_{1},\dots ,x_{k},n)=0\ \land \ \forall 0\leq m\leq n\colon f(x_{1},\dots ,x_{k},m)\downarrow \}}

festgehalten, also die Gesamtheit aller n {\displaystyle n} derart, dass f {\displaystyle f} an der Stelle ( x 1 , … … , x k , n ) {\displaystyle (x_{1},\dots ,x_{k},n)} identisch 0 verschwindet und zusätzlich für alle Punkte ( x 1 , … … , x k , m ) {\displaystyle (x_{1},\dots ,x_{k},m)} mit m ≤ ≤ n {\displaystyle m\leq n} definiert ist.

Zu beachten ist dabei, dass M ( f , x 1 , … … , x k ) {\displaystyle M(f,x_{1},\dots ,x_{k})} als Menge natürlicher Zahlen genau dann ein Minimum besitzt, wenn sie nicht leer ist (vgl. Wohlordnung).

Durch Anwendung des μ μ {\displaystyle \mu } -Operators auf f {\displaystyle f} entstehe nun die partielle Funktion μ μ f : : N k → → N {\displaystyle \mu f\colon \mathbb {N} ^{k}\to \mathbb {N} } , definiert durch:

μ μ f ( x 1 , … … , x k ) = { min M ( f , x 1 , … … , x k ) , falls M ( f , x 1 , … … , x k ) ≠ ≠ ∅ ∅ undefiniert sonst {\displaystyle \mu f(x_{1},\dots ,x_{k})={\begin{cases}\min M(f,x_{1},\dots ,x_{k}),&{\text{falls }}M(f,x_{1},\dots ,x_{k})\neq \emptyset \\{\text{undefiniert}}&{\text{sonst}}\end{cases}}}

Insbesondere bildet der Operator μ μ {\displaystyle \mu } also eine ( k + 1 ) {\displaystyle (k+1)} -stellige partielle Funktion auf eine k {\displaystyle k} -stellige partielle Funktion ab.

Für berechenbares f {\displaystyle f} kann das Programm zur Berechnung von μ μ f {\displaystyle \mu f} verstanden werden als eine While-Schleife, die nach oben zählt und die deswegen nicht terminieren muss:

Parameter: x 1 , … … , x k {\displaystyle x_{1},\ldots ,x_{k}} .

Setze n {\displaystyle n} auf 0 {\displaystyle 0} ;

Solange f ( x 1 , … … , x k , n ) ≠ ≠ 0 {\displaystyle f(x_{1},\dots ,x_{k},n)\neq 0} , erhöhe n {\displaystyle n} um 1 {\displaystyle 1} ;

Ergebnis: n {\displaystyle n} .

Die Klasse P r {\displaystyle Pr} der μ-rekursiven Funktionen ( N k → → N {\displaystyle \mathbb {N} ^{k}\to \mathbb {N} } ) umfasst die folgenden Grundfunktionen:

1. konstante 0-Funktion: f k ( n 1 , … … , n k ) := 0 {\displaystyle f^{k}\left(n_{1},\dots ,n_{k}\right):=0}

2. Projektion auf ein Argument: π π i k ( n 1 , … … , n k ) := n i {\displaystyle \pi _{i}^{k}\left(n_{1},\dots ,n_{k}\right):=n_{i}} , 1 ≤ ≤ i ≤ ≤ k {\displaystyle 1\leq i\leq k}

3. Nachfolgefunktion: ν ν ( n ) := n + 1 {\displaystyle \nu \left(n\right):=n+1}

Die μ-rekursiven Funktionen erhält man als Abschluss der Grundfunktionen bezüglich der drei folgenden Operationen:

1. der Komposition: f ( n 1 , … … , n k ) := g ( h 1 ( n 1 , … … , n k ) , … … , h m ( n 1 , … … , n k ) ) {\displaystyle f\left(n_{1},\dots ,n_{k}\right):=g\left(h_{1}\left(n_{1},\dots ,n_{k}\right),\dots ,h_{m}\left(n_{1},\dots ,n_{k}\right)\right)} , falls g , h 1 , … … , h m ∈ ∈ P r {\displaystyle g,h_{1},\dots ,h_{m}\in Pr}

2. der primitiven Rekursion: f ( 0 , n 2 , … … , n k ) := g ( n 2 , … … , n k ) {\displaystyle f\left(0,n_{2},\dots ,n_{k}\right):=g\left(n_{2},\dots ,n_{k}\right)} und f ( n 1 + 1 , n 2 , … … , n k ) := h ( f ( n 1 , … … , n k ) , n 1 , … … , n k ) {\displaystyle f\left(n_{1}+1,n_{2},\dots ,n_{k}\right):=h\left(f\left(n_{1},\dots ,n_{k}\right),n_{1},\dots ,n_{k}\right)} , falls h , g ∈ ∈ P r {\displaystyle h,g\in Pr}

3. des μ-Operators.

Es lässt sich beweisen, dass eine Turingmaschine (TM) durch μ-rekursive Funktionen simuliert werden kann. Es lässt sich auch beweisen, dass die Menge der μ-rekursiven Funktionen genau der Menge der Turing-berechenbaren Funktionen entspricht.

Man kann zeigen, dass sich die Konfiguration einer TM durch drei Zahlen a {\displaystyle a} , b {\displaystyle b} , c {\displaystyle c} darstellen lässt.

Genau so kann eine Funktion h ( a , b , c ) = y {\displaystyle h(a,b,c)=y} (eine bijektive Abbildung N 3 → → N {\displaystyle \mathbb {N} ^{3}\to \mathbb {N} } ) definiert werden,

die eine geeignete Kodierung der TM ist.

Nehmen wir also eine primitiv-rekursive Funktion

f ( n , x ) = y {\displaystyle f(n,x)=y} ,

die eine geeignete Kodierung der TM liefert für die Eingabe x {\displaystyle x} nach n {\displaystyle n} Berechnungsschritten,

und eine zweite primitiv-rekursive Funktion

g ( y ) = 0 ∨ ∨ g ( y ) = 1 {\displaystyle g(y)=0\lor g(y)=1} ,

die für eine Kodierung y {\displaystyle y} als Ergebnis 0 liefert, falls y {\displaystyle y} einen Endzustand der TM repräsentiert, und ansonsten 1.

Dann ergibt

A n z a h l ( x ) = μ μ ( g ( f ( n , x ) ) ) {\displaystyle \mathrm {Anzahl} (x)=\mu (g(f(n,x)))}

die Anzahl der Schritte, die eine TM zur Berechnung bis zum Ende benötigt. Also bekommen wir mit

B e r e c h n u n g ( x ) = f ( A n z a h l ( x ) , x ) {\displaystyle \mathrm {Berechnung} (x)=f(\mathrm {Anzahl} (x),x)}

die Berechnung der TM in einem Endzustand bei der Eingabe x {\displaystyle x} .

• Die Berechenbarkeit einer μ-rekursiven Funktion bezieht sich auf Werte aus ihrem Definitionsbereich. Es existiert kein allgemeines Verfahren, das alle Werte liefert, die nicht zum Definitionsbereich einer μ-rekursiven Funktion gehören.

• Der μ-Operator realisiert einen Suchprozess, der genau dann abbricht, wenn der gesuchte Wert existiert.

• Alle primitiv-rekursiven Funktionen sind μ-rekursiv.

• Die Ackermannfunktion und die Sudanfunktion sind totale μ-rekursive Funktionen, die nicht primitiv-rekursiv sind.

• Die Funktion Fleißiger Biber (busy beaver) ist nicht μ-rekursiv.

• Die Folge der Ziffern der Halte-Wahrscheinlichkeit (Chaitinsche Konstante Ω Ω {\displaystyle \Omega } ) ist nicht μ-rekursiv. Die Halte-Wahrscheinlichkeit ist definiert durch

Ω Ω := ∑ ∑ p 2 − − | p | {\displaystyle \Omega :=\sum _{p}2^{-\left|p\right|}} ,

wobei p {\displaystyle p} ein haltendes Programm ist und | p | {\displaystyle \left|p\right|} die Länge des Programms in Bit bezeichnet.

• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik (= Spektrum-Hochschultaschenbuch.). 4. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0130-5.

• Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen (= Heidelberger Taschenbücher. 87). 2. Auflage. Springer, Berlin u. a. 1971, ISBN 3-540-05334-4.

• Arnold Oberschelp: Rekursionstheorie. BI-Wissenschaftlicher-Verlag, Mannheim u. a. 1993, ISBN 3-411-16171-X.

• Wolfgang Rautenberg: Einführung in die Mathematische Logik. Ein Lehrbuch. 3., überarbeitete Auflage. Vieweg + Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2.